

class Solution {
    using ll = long long;
    vector<int> tmp;
    ll cnt = 0;
    ll g_cnt = 0;
    ll n;
public:
    void mergeSort(vector<int>& nums, int begin, int end)
    {
        if (begin >= end - 1) return;

        int mid = (begin + end) >> 1;

        mergeSort(nums, begin, mid);
        mergeSort(nums, mid, end);
        int i = begin, j = mid, k = 0;
        for (; i < mid && j < end; k++)
        {
            if (nums[j] < nums[i])
            {
                g_cnt += mid - i;
                tmp[k] = nums[j++];
            }
            else
            {
                tmp[k] = nums[i++];
            }
        }
        for (; i < mid; i++, k++)
        {
            tmp[k] = nums[i];
        }
        for (; j < end; j++, k++)
        {
            tmp[k] = nums[j];
        }

        for (int left = begin, k = 0; left < end; left++, k++)
        {
            nums[left] = tmp[k];
        }
    }

    bool isIdealPermutation(vector<int>& nums)
    {
        n = nums.size();
        tmp.resize(n);
        for (int i = 1; i < n; i++)
        {
            if (nums[i - 1] > nums[i])
            {
                cnt++;
            }
        }

        mergeSort(nums, 0, n);
        return cnt == g_cnt;
    }
};